package newcoder_exp.justPractise;

import org.junit.Test;

import utils.ArrayGenerator;

public class NC144 {
    public class Solution {
        public long subsequence (int n, int[] array) {
            //f[i]表示到达i的最大不相邻子序和
            long[] f = new long[n];
            f[0] = array[0];
            f[1] = array[1];
            long last = Integer.MIN_VALUE;
            long res = Integer.MIN_VALUE;
            for (int i = 2; i < n; i++) {
                last = Math.max(f[i - 2], last);
                f[i] = last + array[i];
                res = Math.max(res, f[i]);
            }
            return res;
        }

        public long subsequence2 (int n, int[] array) {
            // write code here   
            long[] dp = new long[n + 1];      
            dp[0] = 0;
            dp[1] = array[0];      
            for (int i = 2; i <= n; i++) {
                dp[i] = Math.max(dp[i-1],   dp[i-2] + array[i-1]);
            }
            return dp[n];
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        for (int i = 0; i < 10000; i++) {
            int[] nums = ArrayGenerator.getArray(100, 20);       
            System.out.print(s.subsequence(20, nums) != s.subsequence2(20, nums) ? "FUCk" : "");
        }
    }
}
